package Hot100.DP;

public class BL_coinChange {

    public static void main(String[] args) {
        int coins[] = {1,2,3};
        int amount = 3;

        System.out.println( new BL_coinChange().coinChange(coins,amount));
    }
    int min = Integer.MAX_VALUE;
    int step = 1;

    public int coinChange(int[] coins, int amount) {
        String route = "";
        for (int i = 0; i < coins.length; i++) {
            coin_BL(coins,coins[i],amount,step,route);
        }
        if(min != Integer.MAX_VALUE){
            return min;
        }else {
            return  -1;
        }
    }
    public void coin_BL(int coins[],int coin,int amount,int step,String route){
        route += String.valueOf(coin);
        if(amount - coin == 0){
            System.out.println(route);
            route = route.substring(0,route.length() - 1);
            if(step < min){
                min = step;
                return;
            }
        }else if(amount - coin < 0){
            route = route.substring(0,route.length() - 1);
            return;
        }
        for (int i = 0; i < coins.length; i++) {

            coin_BL(coins,coins[i],amount - coin,step + 1,route);
        }
    }
}
